\documentclass[a4paper,12pt,twocolumn]{article}
\usepackage{graphicx}
\usepackage{listings}
\usepackage[justification=centering]{caption}
\usepackage{subfigure}  
\usepackage{multirow}
\usepackage{balance}
\usepackage{gensymb}
\lstset{language=Matlab}
\lstset{breaklines}
\lstset{extendedchars=false}

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\theoremstyle{definition}
\newtheorem{thm}{Theorem}
\newtheorem{exmp}{Example}
\newtheorem{defn}{Definition}
\newtheorem{lema}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{coro}{Corollary}


\renewcommand{\baselinestretch}{1.25}

%------------setlength----------------%
\setlength{\textwidth}{162mm}
%\setlength{\textheight}{190mm}
\setlength{\textheight}{231mm}
\setlength{\headheight}{-0.1cm}
\setlength{\topmargin}{-0.1cm}
\setlength{\oddsidemargin}{-0cm}
\setlength{\evensidemargin}{-0cm}

\setlength\columnsep{12pt}
\setlength\columnseprule{0.4pt}

\setlength{\parskip}{1mm}
\setlength{\unitlength}{1mm}
\setlength{\parindent}{2em}

\title{Numerical Analysis Homework \#3}

\author{Li Zhiqi\quad 3180103041 , }

\begin{document}
\maketitle
\section{Theoretical questions}
\uppercase\expandafter{\romannumeral1}.\\
Notice that $$p(0) = 0 , p(1) = 1 , p'(1) = -3 , p''(1) = 6.$$
Then
  \begin{align*}
    p(x) &= p(1) + p'(1)(x - 1) + \frac{ p''(1)}{2}(x - 1)^2 \nonumber \\
    &+ a(x - 1)^3 \nonumber\\
    &=1 - 3(x - 1) + 3(x - 1)^2 + a(x - 1)^3. \nonumber 
  \end{align*}
  Substitute the consdition $s(0) = 0$, we have
  \begin{align*}
    0 = 1 - (-3) + 3 -a \Rightarrow a = 7. \nonumber
  \end{align*}
  Hence
  \begin{align*}
    p(x) &= 1 - 3(x - 1) + 3(x - 1)^2 + 7(x - 1)^3\nonumber \\
         &=7x^3-18x^2+12x^2 \quad \forall x \in [0,1]. \nonumber 
  \end{align*}
  Compute that $s''(0) = -36 \ne 0$, so $s(x)$ is not a natural cubic spline.\\\\
\uppercase\expandafter{\romannumeral2}.\\
(a)According from Theorem 4.14, the dimension of $\mathbb{S}_2^1$ is
$n + 1$. Apart from the $n$ interpolation conditions at
$x_1,x_2,\cdots,x_n$, an additional condition is needed to determine
$s$ uniquely.\\
(b)We show the interpolation table as follows:\\
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{0.6mm}{
	\begin{tabular}{c|c c c}
		$x_i\ $ & $f_i\ $ &  &\\	
		$x_i\ $ & $f_i\ $ & $m_i\ $ &\\			
                $x_{i+1}\ $ & $f_{i+1}\ $ & $K_i\ $ & $\frac{K_i - m_i}{x_{i+1}-x_i}\ $\\
	\end{tabular}
}
\end{table}\\
where $K_i = f[x_i,x_{i+1}]$.\\
Then
\begin{align*}
  \quad p_i(x) = f_i + (x - x_i)m_i + (x - x_i)^2\frac{K_i - m_i}{x_{i+1}-x_i}.
\end{align*}
(c)\ By (b), $s'_{i-1}(x_i) = s'_i(x_i)$ implies
\begin{align*}
  m_i + m_{i-1} = 2f[x_{i-1},x_i].
\end{align*}
Hence $m_2,m_3,\cdots,m_{n-1}$ can be computed successively by
$$m_i = 2f[x_{i-1},x_i] - m_{i-1},\quad i = 2,3,\cdots,n-1,$$
where $m_1 = f'(a)$.\\\\
\uppercase\expandafter{\romannumeral3}.\\
Notice that $s_2(0) = s_1(0) = 1 + c, s_2'(0) = s_1'(0) = 3c, s_2''(0)
= s_1''(0) = 6c$, and natural condition implies $s_2''(1) = 0$.\\
By Taylor formula, we assume
\begin{align*}
  s_2(x) &= s_2(0) + xs_2'(0) + \frac{x^2}{2}s_2''(0) + ax^3\\
  &= ax^3 + 3cx^2 + 3cx + c + 1,
\end{align*}
Substitute the consdition $s_2''(1) = 0$, we have
$$s_2''(1) = 6a + 6c = 0 \Rightarrow a = -c.$$
Hence
$$s_2(x) = -cx^3 + 3cx^2 + 3cx + c + 1, \ x\in[0,1] .$$
When $s(1) = -1$ holds,
$$s_2(1) = -c + 3c + 3c + c + 1 = -1 \Rightarrow c = -\frac{1}{3}.$$
Namely $c = -\frac{1}{3}$.\\\\
\uppercase\expandafter{\romannumeral4}.\\
(a) For $s_1$ in $[-1,0]$ and $s_2$ in $[0,1]$, notice that $s_1(-1) =
\cos(-\frac{\pi}{2}) = 0, s_1(0) = s_2(0) = \cos(0) = 1, s_1'(0) = s_2'(0),s_1''(0)
= s_2''(0)$ and $s_2(1) = \cos(\frac{\pi}{2}) = 0$. Natural condition
implies $s_1''(-1) = s_2''(1) = 0$.\\
By Taylor formula, we assume
\begin{align*}
  s_2(x) &= s_2(1) + a(x-1) + \frac{(x-1)^2}{2}s_2''(1) \\
  &+ b(x-1)^3\\
  &= b(x-1)^3 + a(x-1), \quad x\in[0,1]
\end{align*}
and
\begin{align*}
  s_1(x) &=s_1(-1) + c(x+1) + \frac{(x+1)^2}{2}s_1''(-1) \\
  &+ d(x+1)^3\\
  &= d(x+1)^3 + c(x+1), \quad x\in[-1,0]
\end{align*}
Then conditions $s_2(0) = 1,s_1(0) = 1, s_1'(0) = s_2'(0)$ and $s_1''(0)
= s_2''(0)$ imply respectively
$$\left\{\begin{matrix}
  -a-b&=  &1 \\
  c+d&=  &1 \\
  c+3d&=  &a+3b \\
  6d&=  &-6b
\end{matrix}\right.
   \Rightarrow
\left\{\begin{matrix}
  a&=  &-\frac{3}{2} \\
  b&=  &\frac{1}{2} \\
  c&=  &\frac{3}{2} \\
  d&=  &-\frac{1}{2}
\end{matrix}\right. $$
Hence
\begin{align*}
  s_1(x) &= -\frac{1}{2}(x+1)^3 + \frac{3}{2}(x+1)\\
         &=-\frac{1}{2}x^3 + -\frac{3}{2}x^2+1, \quad  x\in[-1,0],\\
  s_2(x) &= \frac{1}{2}(x-1)^3 - \frac{3}{2}(x-1)\\
         &=\frac{1}{2}x^3-\frac{3}{2}x^2 + 1, \quad x\in[0,1].    
\end{align*}
(b) To get $g(x)$, consider the interpolation table as follows.
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{0.6mm}{
	\begin{tabular}{c|c c c}
		$-1\ $ & $0\ $ &  &\\	
		$0\ $ & $1\ $ & $1\ $ &\\			
                $1\ $ & $0\ $ & $-1\ $ & $-1\ $\\
	\end{tabular}
}
\end{table}\\
Hence $g(x) = 0 + (x+1) -x(x+1) = -x^2 + 1$.
$$E_1 = \int_{-1}^{1}[g''(x)]^2dx = \int_{-1}^14dx = 8. $$
On the other hand,
$$f''(x) = \begin{cases}
 -3x - 3 \quad x\in[-1,0],\\
 3x - 3 \quad x\in[0,1],
\end{cases}$$
hence
$$E_2 = \int_{-1}^0(-3x-3)^2dx + \int_0^1(3x-3)^2dx = 6 < E_1,$$
which complete the verification.\\\\
\uppercase\expandafter{\romannumeral5}.\\
(a) We have known
$$B_i^1(x) = \begin{cases}
 \frac{x-t_{i-1}}{t_i - t_{i-1}} \quad x\in(t_{i-1},t_i],\\
 \frac{t_{i+1}-x}{t_{i+1}-t_i} \quad x\in(t_i,t_{i+1}],\\
 0 \quad \quad otherwise,
\end{cases}$$
by Example 4.24 and Definition 4.21. Apply Definition 4.23, we have
\begin{align*}
  &B_i^2(x) = \frac{x-t_{i-1}}{t_{i+1} - t_{i-1}}B_i^1(x) +
             \frac{t_{i+2}-x}{t_{i+2} - t_i}B_{i+1}^1(x)\\
  &=\begin{cases}
 \frac{(x-t_{i-1})^2}{(t_{i+1}-t_{i-1})(t_i - t_{i-1})} \quad x\in(t_{i-1},t_i],\\
 \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)}\\
 \quad \quad \quad \quad \quad \quad\quad \quad x\in(t_i,t_{i+1}],\\
 \frac{(t_{i+2}-x)^2}{(t_{i+2}-t_{i})(t_{i+2} - t_{i+1})}, \quad x\in(t_{i+1},t_{i+2}],\\
 0 \quad \quad otherwise.
\end{cases}
\end{align*}
(b) Explicit expression of $B_i^2(x)$ in (a) implies
\begin{align*}
  &\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x) \\
  &= \begin{cases}
 \frac{2(x-t_{i-1})}{(t_{i+1}-t_{i-1})(t_i - t_{i-1})} \quad x\in(t_{i-1},t_i],\\
 \frac{-2x+t_{i+1}+t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{-2x+t_{i+2}+t_i}{(t_{i+2}-t_{i})(t_{i+1}-t_i)}\\
 \quad \quad \quad \quad \quad \quad\quad \quad x\in(t_i,t_{i+1}],\\
 \frac{-2(t_{i+2}-x)}{(t_{i+2}-t_{i})(t_{i+2} - t_{i+1})}, \quad x\in(t_{i+1},t_{i+2}],\\
 0 \quad \quad otherwise.
\end{cases}
\end{align*}
Then
\begin{align*}
  &\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(t_i)^- =
  \frac{2}{t_{i+1}-t_{i-1}} = \frac{\mathrm{d}}{\mathrm{d} x}
  B_i^2(t_i)^+,\\
  &\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(t_{i+1})^- =
  \frac{-2}{t_{i+2}-t_{i}} = \frac{\mathrm{d}}{\mathrm{d} x}
  B_i^2(t_{i+1})^+.
\end{align*}
We verify that $\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x) $ is
continuous at $t_i$ and $t_{i+1}$.\\
(c) $\forall x \in (t_{i-1},t_i] $, apparently
$\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x) > 0$. So we take attention
to interval $(t_i,t_{i+1})$.\\
Notice that $\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x)$ is linear in
$(t_i,t_{i+1})$, and $\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(t_i) >
0,\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(t_{i+1}) < 0$. Therefore there
exists unique $x^*\in (t_i,t_{i+1})$ such that
$\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x^*) = 0$.\\
Let $\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x^*) = 0$, we get
$$x^* =
\frac{t_{i+2}t_{i+1}-t_it_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}}.$$
(d) By (b),(c), we have known
\begin{align*}
  &\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x) > 0,\quad x\in
    (t_{i-1},x^*),\\
    &\frac{\mathrm{d}}{\mathrm{d} x} B_i^2(x) < 0,\quad x\in
    (x^*,t_{i+2}).
\end{align*}
Combine the fact that the support of $B_i^2(x)$ is $[t_{i-1},t_{i+2}]$
by Lemma 4.27, we just need to show $B_i^2(x^*) < 1$.\\
By computing we get
$$B_i^2(x^*) = \frac{t_{i+2}-t_{i-1}}{t_{i+2}-t_{i-1}+(t_{i+1}-t_i)}
< 1,$$
which completes the proof.\\
(e) The ploting result is as follows.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Output/F1.eps}
	\caption{$B_1^2(x)$}
\end{figure}\\
\uppercase\expandafter{\romannumeral6}.\\
By Theorem 3.17,
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=[t_i,t_{i+1},t_{i+2}](t - x)_+^2 - [t_{i-1},t_i,t_{i+1}](t -
    x)_+^2\\
  &=\frac{[t_{i+1},t_{i+2}](t - x)_+^2-[t_i,t_{i+1}](t -
    x)_+^2}{t_{i+2} - t_{i}}\\
  &\ -\frac{[t_i,t_{i+1}](t - x)_+^2 - [t_{i-1},t_i](t -
     x)_+^2}{t_{i+1}-t_{i-1}}\\
  &=\frac{(t_{i+2}-x)_+^2-(t_{i+1}-x)_+^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}-\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)_+^2-(t_{i}-x)_+^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}+\frac{(t_{i}-x)_+^2-(t_{i-1}-x)_+^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}.
\end{align*}
When $x\in(-\infty,t_{i-1}]$, the fact that $(t_{i-1}-x)_+^2 = (t_{i-1}-x)^2,
(t_{i}-x)_+^2 = (t_{i}-x)^2, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}\\
  &\ +\frac{(t_{i}-x)^2-(t_{i-1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{t_{i+2}+t_{i+1}+2x}{t_{i+2}-t_{i}} -
    \frac{t_{i+1}+t_{i}+2x}{t_{i+2}-t_{i}}\\
  &\ -\frac{t_{i+1}+t_{i}+2x}{t_{i+1}-t_{i-1}}  +\frac{t_{i}+t_{i-1}+2x}{t_{i+1} - t_{i-1}}\\
  &= 0 = B_i^2(x), \quad x\in (-\infty,t_{i-1}].
\end{align*}
When $x\in(t_{i-1},t_i]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = (t_{i}-x)^2, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2-(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}\\
  &\ +\frac{(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{t_{i+2}+t_{i+1}+2x}{t_{i+2}-t_{i}} -
    \frac{t_{i+1}+t_{i}+2x}{t_{i+2}-t_{i}}\\
  &\ -\frac{t_{i+1}+t_{i}+2x}{t_{i+1}-t_{i-1}}  +\frac{(t_{i}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})}\\
  &= \frac{(t_{i-1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i} -
    t_{i-1})} = B_i^2(x), \\
  &\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x\in (t_{i-1},t_i].
\end{align*}
Similarily, when $x\in(t_i,t_{i+1}]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = 0, (t_{i+1}-x)_+^2 = (t_{i+1}-x)^2$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2-(t_{i+1}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})}\\
  &\ -\frac{(t_{i+1}-x)^2}{(t_{i+2} -
    t_{i})(t_{i+1} - t_{i})}\\
  &\ -\frac{(t_{i+1}-x)^2}{(t_{i+1} - t_{i-1})(t_{i+1} -
    t_{i})}\\
  &= \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}\\
  &\ +\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)} = B_i^2(x),\ x\in (t_{i},t_{i+1}].
\end{align*}
When $x\in(t_{i+1},t_{i+2}]$, the fact that $(t_{i-1}-x)_+^2 = 0,
(t_{i}-x)_+^2 = 0, (t_{i+1}-x)_+^2 = 0$ and
$(t_{i+2}-x)_+^2 = (t_{i+2}-x)^2$ imply
\begin{align*}
  &(t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2\\
  &=\frac{(t_{i+2}-x)^2}{(t_{i+2} - t_{i})(t_{i+2} -
    t_{i+1})} = B_i^2(x),\ x\in (t_{i+1},t_{i+2}].
\end{align*}
Lastly, when $x\in(t_{i+2},\infty)$, all terms equal to 0 and the
conclusion is apparently holds.\\
In conclusion, we have verified
\begin{align*}
  (t_{i+2} - t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t - x)_+^2 = B_i^2.
\end{align*}
\uppercase\expandafter{\romannumeral7}.\\
From Theorem 4.34, we do integral at both sides and get
\begin{align*}
  0 &= B_i^n(t_{i+n}) - B_i^n(t_{i-1}) = \int_{t_{i-1}}^{t_{i+n}}
  \frac{\mathrm{d} }{\mathrm{d} x} B_i^n(x)dx\\
  &= \frac{n\int_{t_{i-1}}^{t_{i+n}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    -
    \frac{n\int_{t_{i-1}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}}\\
  &=\frac{n\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    -
    \frac{n\int_{t_{i}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}},
\end{align*}
where the first and last equation come from the fact that the support
of $B_i^n$ is $[t_{i-1},t_{i+n}]$, and the second equation from
fundamental theorem of calculus.\\
Hence we have
$$\frac{\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}}
    =
\frac{\int_{t_{i}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx}{t_{i+n}-t_{i}}.$$
By induction,
\begin{align*}
\forall i \in \mathbb{Z} ,
  \frac{\int_{t_{i-1}}^{t_{i+n-1}}B_i^{n-1}(x)dx}{t_{i+n-1}-t_{i-1}} =
  s(n) \ ( = \frac{1}{n}),  
\end{align*}
where $s(n)$ is independent of $i$. Therefore the scaled integral of a B-spline $B_i^n(x)$ over its
support is independent of its index $i$.\\\\    
\uppercase\expandafter{\romannumeral8}.\\    
(a) Compute that
\begin{align*}
  &[x_i,x_{i+1},x_{i+2}]x^4\\
  &=\frac{[x_{i+1},x_{i+2}]x^4-[x_i,x_{i+1}]x^4}{x_{i+2}-x_i}\\
  &=\frac{x_{i+2}^4 - x_{i+1}^4}{(x_{i+2}-x_i)(x_{i+2}-x_{i+1})}\\
  &\ - \frac{x_{i+1}^4 - x_{i}^4}{(x_{i+2}-x_i)(x_{i+1}-x_{i})}\\
  &=\frac{(x_{i+2}^2+x_{i+1}^2)(x_{i+2}+x_{i+1})}{x_{i+2}-x_i} \\
  &\ - \frac{(x_{i+1}^2+x_{i}^2)(x_{i+1}+x_{i})}{x_{i+2}-x_i} \\
  &=x_{i+2}^2+x_{i+2}x_{i+1}+x_{i+2}x_i\\
  &\ + x_{i+1}^2+x_{i}^2+x_{i+1}x_i\\
  &=\tau_2(x_i,x_{i+1},x_{i+2}).    
\end{align*}
(b) We use induction to complete the proof. When $n = 0$, $\tau_m(x_i)
= [x_i]x^m$ apparently holds. Suppose that the conclusion holds for
$0,1,\cdots,n-1$, then
\begin{align*}
  &\tau_{m-n}(x_i,x_{i+1},\cdots,x_{i+n})\\
  &=\frac{\tau_{m-n+1}(x_{i+1},\cdots,x_{i+n}) - \tau_{m-n+1}(x_i,\cdots,x_{i+n-1})}{x_{i+n} - x_i} \\
  &=\frac{[x_{i+1},\cdots,x_{i+n}]x^m-[x_i,\cdots,x_{i+n-1}]x^m}{x_{i+n}
    - x_i}\\
  &=[x_i,x_{i+1},\cdots,x_{i+n}]x^m,
\end{align*}
where the first equation comes from the fact that
\begin{align*}
  &(x_n - x_1)\tau_m(x_1,\cdots,x_n) \\
  &= \tau_{m+1}(x_2,\cdots,x_n) - \tau_{m+1}(x_1,\cdots,x_{n-1}),
\end{align*}
which can be easily implied by the recursive relation on complete
symmetric polynomials. The second equation comes from induction
hypothesis. So far we have completed the induction.
    
\newpage
\section{C++ programming}
A. Use \textbf{"make"} to generate and run an executable called
\textbf{main}, which is the answer to the questions.\\ 
Use \textbf{"make run"} to run the .m file and show all the numerical results and graphics by matlab. You're supposed to exit matlab to get the next plot.\\
Use \textbf{"make testall"} to generate and run all the test file. The result will be shown immediately. \\
Use \textbf{"make doc"} to generate a pdf file called \textbf{doc.pdf}, which gives the answer to theoretical questions and explanations for programming questions.\\\\
B. For complete condition:
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Output/F2.eps}
	\caption{cubic spline with complete condition}
\end{figure}\\
We list the errors and convergence rates here.\\
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{2mm}{
          \begin{tabular}{c|c   c   c   c   c}
            \hline
          & $n = 6$ & ratio & $n = 11$ & ratio & $n = 21$\\
          \hline
          $\left \| E \right \|_{\infty}$  & 4.22e-1 & 4.36 & 2.05e-2 & 2.70 & 3.17e-3\\
          \hline
          & $n = 21$ & ratio & $n = 41$ & ratio & $n = 81$\\
          \hline
          $\left \| E \right \|_{\infty}$ & 3.17e-3 & 3.52 & 2.75e-4&
                                                                      4.10 & 1.61e-5\\
          \hline
	\end{tabular}
        \caption{complete cubic spline : errors and convergence rates}
}
\end{table}\\
\newpage
\noindent For not-a-knot condition:
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Output/F3.eps}
	\caption{cubic spline with not-a-knot condition}
\end{figure}\\
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{2mm}{
          \begin{tabular}{c|c   c   c   c   c}
            \hline
          & $n = 6$ & ratio & $n = 11$ & ratio & $n = 21$\\
          \hline
          $\left \| E \right \|_{\infty}$  & 4.32e-1 & 4.39 & 2.05e-2 & 2.70 & 3.17e-3\\
          \hline
          & $n = 21$ & ratio & $n = 41$ & ratio & $n = 81$\\
          \hline
          $\left \| E \right \|_{\infty}$ & 3.17e-3 & 3.52 & 2.75e-4&
                                                                      4.10 & 1.61e-5\\
            \hline
	\end{tabular}
        \caption{not-a-knot cubic spline : errors and convergence rates}
}
\end{table}\\
\newpage
\noindent C. The plot results are as following.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Output/F4.eps}
	\caption{$S_1$ : cardinal B-spline for Corollary 4.58}
      \end{figure}\\
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8cm]{Output/F5.eps}
	\caption{$S_2$ : cardinal B-spline for Corollary 4.59}
      \end{figure}\\
      \newpage
\noindent D. The values of $E_S(x)$ are as following.      
\begin{table}[!htp]
	\centering
	\setlength{\tabcolsep}{2mm}{
          \begin{tabular}{c|c|c}
            \hline
          $x$ & $E_{S_1}(x)$ & $E_{S_2}(x)$ \\
          \hline
          $-3.5$  & $1.34\times10^{-3}$ & $0$ \\
          \hline
          $-3$  & $1.39\times10^{-17}$ & $1.42\times10^{-3}$ \\
          \hline
          $-0.5$  & $2.05\times10^{-2}$ & $1.11\times10^{-16}$ \\
          \hline
          $0$  & $0$ & $0.1202$ \\
          \hline
          $0.5$  & $2.05\times10^{-2}$ & $1.11\times10^{-16}$ \\
          \hline
          $3$  & $1.39\times10^{-17}$ & $1.42\times10^{-3}$ \\
          \hline
          $3.5$  & $6.70\times10^{-4}$ & $0$ \\
          \hline
	\end{tabular}
        \caption{values of $E_S(x)$ for two cardinal B-splines in C}
}
\end{table}\\
We find that the error of $S_1$ reaches machine precision at -3, 0 and 3, while $S_2$ does the same at -3.5, -0.5, 0.5 and 3.5. That's because these points are interpolation points for two splines respectively.\\
Notice that $S_2$ performes badly near 0, therefore $S_1$ is more
accurate.\\\\
E. We take $\frac{2}{3}$ points on part that $y > 1$ to capture more
details, and take rest points on another part. For boundary
conditions, we use complete condition on $(0,-1)$ and $(0,1)$ to
maintain the sharpness.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=9cm]{Output/F6.eps}
	\caption{heart function for $n = 10,40,160$}
      \end{figure}\\
\newpage      
\noindent F. The three complete cubic splines can be obtained by using "make
main" and "./main" or directly "make". We only show the plot result here.
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=8.5cm]{Output/F7.eps}
	\caption{the upper portion of the noble beast}
      \end{figure}\\
\newpage 
\noindent G. For $n = 1$:
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=9cm]{Output/F8.eps}
	\caption{table of divided difference for truncated power
          functions, $n = 1$}
      \end{figure}\\
For $n = 2$:
\begin{figure}[!htp]   
	\centering
	\includegraphics[width=9cm]{Output/F9.eps}
	\caption{table of divided difference for truncated power
          functions, $n = 2$}
      \end{figure}\\      
\end{document}
